perm filename 2[00,BGB]2 blob
sn#043254 filedate 1973-05-23 generic text, type C, neo UTF8
COMMENT ā VALID 00018 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 PAGE 21. FIGURES: PUMP VIDEO & PUMP VECTOR CONTOURS.
C00004 00003 PAGE 22. THE ALGORITHM: INTRODUCTION.
C00006 00004 PAGE 23. FIGURES.
C00007 00005 PAGE 24. 1. THRESHOLDING.
C00010 00006 PAGE 25. FIGURES. DEKINKING ILLUSTRATED.
C00011 00007 PAGE 26. 2. CONTOURING.
C00017 00008 PAGE 27. FIGURES: NESTING ILLUSTRATED.
C00018 00009 PAGE 28. 3. NESTING.
C00023 00010 Let the given polygon be named Poly and let the surrounder
C00025 00011 PAGE 29. NESTING ILLUSTRATED. CONTINUED.
C00026 00012 PAGE 30. NESTING CONTINUED.
C00027 00013 PAGE 31. FIGURES: RECURSIVE SMOOTHING ILLUSTRATED.
C00028 00014 PAGE 32. 4. SMOOTHING.
C00031 00015 PAGE 33. FIGURES: COMPARING ILLUSTRATED.
C00032 00016 PAGE 34. 5. COMPARING.
C00034 00017 PAGE 35. LAMINA INERTIA TENSOR.
C00035 00018 PAGE 36. PERFORMANCE.
C00036 ENDMK
Cā;
PAGE 21. FIGURES: PUMP VIDEO & PUMP VECTOR CONTOURS.
PAGE 22. THE ALGORITHM: INTRODUCTION.
CRE consists of five steps: thresholding, contouring,
nesting, smoothing and comparing. Thresholding, contouring and
smoothing perform conversions between two different kinds of images.
Nesting and contouring compute topological relationships within a
given image representation. In summary the major operations are:
MAJOR OPERATION. OPERAND. RESULT.
1. THRESHOLDING: 6-BIT-IMAGE, 1-BIT-IMAGES.
2. CONTOURING: 1-BIT-IMAGES, VIC-IMAGE.
3. NESTING: VIC-IMAGE, NESTED-VIC-IMAGE.
4. SMOOTHING: VIC-IMAGE, ARC-IMAGE.
5. COMPARING: IMAGE & FILM, FILM.
Although the natural order of operations is sequential from
image thresholding to image comparing; in order to keep memory size
down, the first four steps are applied one intensity level at a time
from the darkest cut to the lightest cut (only nesting depends on
this sequential cut order). However, comparing is applied to whole
images.
The illustrations on pages 21 and 23 show a video image and its
initial sawtooth contours; the illustrations immediately below and
on page 24 illustrate the smoothed arc contours generated by CRE.
FIGURE: PUMP ARC CONTOURS.
PAGE 23. FIGURES.
DBA'S TOMBSTONE VIDEO.
DBA'S SMOOTHED CONTOURS.
PAGE 24. 1. THRESHOLDING.
Thresholding, the first and easiest step, consists of two
subroutines, called THRESH and PACXOR. THRESH converts a 6-bit
image into a 1-bit image with respect to a given threshold cut level
between zero for black and sixty-three for light. All pixels equal
to or greater than the cut, map into a one; all the pixels less than
the cut, map into zero. The resulting 1-bit image is stored in a bit
array of 216 rows by 288 columns (1728 words) called the PAC
(picture accumulator) which was named in memory of McCormick's
ILLIAC-III. After THRESH, the PAC contains blobs of bits. A blob
is defined as "rook's move" simply connected; that is every bit of a
blob can be reached by horizontal or vertical moves from any other
bit without having to cross a zero bit or to make a diagonal
(bishop's) move. Blobs may of course have holes. Or equalvalently a
blob always has one outer perimeter polygon, and may have one,
several or no inner perimeter polygons. This blob and hole topology
is recoverible from the CRE data structure and is built by the
nesting step.
Next, PACXOR copies the PAC into two slightly larger bit
arrays named HSEG and VSEG. Then the PAC is shifted down one row and
exclusive OR'ed into the HSEG array; and the PAC is shifted right
one column and exclusive OR'ed into the VSEG array to compute the
horizontal and vertical border bits of the PAC blobs. Notice, that
this is the very heart of the "edge finder" of CRE. Namely, PACXOR
is the mechanism that converts regions into edges.
PAGE 25. FIGURES. DEKINKING ILLUSTRATED.
PAGE 26. 2. CONTOURING.
Contouring, converts the bit arrays HSEG and VSEG into
vectors and polygons. The contouring itself, is done by a single
subroutine named MKPGON, make polygon. When MKPGON is called, it
looks for the upper most left non-zero bit in the VSEG array. If the
VSEG array is empty, MKPGON returns a NIL. However, when the bit is
found, MKPGON traces and erases the polygonal outline to which that
bit belongs and returns a polygon node with a ring of vectors.
To belabor the details (for the sake of later complexities);
the MKGON trace can go in four directions: north and south along
vertical columns of bits in the VSEG array, or east and west along
horizontal rows of the HSEG array. The trace starts by heading south
until it hits a turn; when heading south MKPGON must check for first
a turn to the east (indicated by a bit in HSEG); next for no turn
(continue south); and last for a turn to the west. When a turn is
encountered MKPGON creates a vector node representing the run of
bits between the previous turn and the present turn. The trace
always ends heading west bound. The outline so traced can be either
the edge of a blob or a hole, the two cases are distinguished by
looking at the VIC-polygon's upper left most pixel in the PAC bit
array.
There are two complexities: contrast accumulation and
dekinking. The contrast of a vector is defined as (QUOTIENT
(DIFFERENCE (Sum of pixel values on one side of the vector)(Sum of
pixel values on the other side ofthe vector)) (length of the vector
in pixels)). Since vectors are always either horizontal or vertical
and are construed as being on the cracks between pixels; thus the
specified summations refer to the pixels immediatelt to either side
of the vector. Notice that this definition of constrast will always
give a positive constrast for vectors of a blob and negative
contrast for the vectors of a hole.
The terms "jaggies", "kinks" and "sawtooth" all are used to
express what seems to be wrong about the uppermost left polygon on
page 25. The problem involves doing something to a rectilinear
quantized set of segments, to make its linear nature more evident.
The CRE jaggies solution (in the subroutine MKPGON) merely positions
the turning locus diagonally off its grid point alittle in the
direction (northeast, northwest, southwest or southeast) that
bisects the turn's right angle. The distance of dekink vernier
positioning is always less than half a pixel; but greater for
brighter cuts and less for the darker cuts; in order to preserve the
nesting of contours.
PAGE 27. FIGURES: NESTING ILLUSTRATED.
1ST FRAME FLAT NEST.
2ND FRAME GEOMED NEST.
PAGE 28. 3. NESTING.
The nesting problem is to decide whether one contour polygon
is within another. Although easy in the two polygon case; solving
the nesting of many polygons with respect to each other becomes
n-squared expensive in either compute time or in memory space. The
nesting solution in CRE sacrifices memory for speed and requires a
31K array, called the SKY.
CRE's accumulation of a properly nested tree of polygons
depends on the order of threshold cutting going from dark to light.
For each polygon there are two nesting steps: first, the polygon is
placed in the tree of nested polygons by the subroutine INTREE;
second, the polygon is placed in the SKY array by the subroutine
named INSKY.
The SKY array is 216 rows of 288 columns of 18-bit pointers.
The name "SKY" came about because, the array used to represent the
furthest away regions or background, which in the case of a robot
vehicle is the real sky blue. The sky contains vector pointers; and
would be very efficient on on a virtual memory machine that didn't
allocate unused pages of its address space. Whereas most computers
have more memory containers than address space; computer graphics
and vision might be easier to program in a memory with more address
space than physical space; i.e. an almost empty virtual memory.
The first part of the INTREE routine finds the surrounder of
a given polygon by scanning the SKY due east from the uppermost left
pixel of the given polygon. The SON of a polygon is always its
uppermost left vector. After INTREE, the INSKY routine places
pointers to the vertical vectors of the given polygon into the sky
array.
The second part of the INTREE routine checks for and fixes
up the case where the new polygon captures a polygon that is already
enclaved. This only happens when two or more levels of the image
have blobs that have holes. The rest of this section is devoted to
the arcane details of fixing up the tree link of multi level hole
polygons.
Let the given polygon be named Poly; and let the surrounder
of Poly be called Exopoly; and assume that Exopoly surrounds a
a several hole polygon
named Hole1, Hole2, etc.; which are already in the nested polygon tree.
That is Hole1 is the ENDO of Exopoly's; and is one of a ring of holes called
the ENDO ring of Exopoly.
Now the subrotine INTREE must re-scan the sky array
for the EXO's of all the polygons on
Exopoly's ENDO ring.
On such rescanning there are four cases:
1. No change: the scan returns Exopoly; which is the hole's
original EXO.
2. Poly captures Hole; the scan returns Poly indicating
the Endo has been captured by POLY;
3. My brothers fate; the ENDO hits an endo which
is not on the P-list.
4. My fate delayed;
Since deep holes frequently occur in natural images, (even in
images of pears and apples) I was amused to see that not a single deep
hole occurs in the examples in Krakauer's thesis which was about
nested polygon trees of video intensity contours.
PAGE 29. NESTING ILLUSTRATED. CONTINUED.
PAGE 30. NESTING CONTINUED.
PAGE 31. FIGURES: RECURSIVE SMOOTHING ILLUSTRATED.
PAGE 32. 4. SMOOTHING.
In CRE the term "smoothing" refers more to the
problem of breaking a manifold up into functions, rather than to the
problem of fitting functions to measured data.
The smoothing step in CRE, converts the polygons of vertical
and horizontal vectors into polygons of arcs. For the present the
term "arc" means "linear arc" which is a line segment. Fancier arcs:
circular and cubic spline were tried and found expensive to compute
and unwieldly to manipulate; however fancy arcs were doomed by the
fact that after going to all the trouble of implementing and
computing them, there remained the overpowering demand to break them
down again into linear vectors for computing areas, inertia tensors
or mere display buffers.
To start, a ring of two arcs is formed (a bi-gon) with one
arc at the uppermost left and the other at the lowermost right of
the given polygon of vectors. Now the smoothing operation is
recursive; each arc is in one to one correspondece with a list of
vectors; if each point on the list of vectors is close enough to the
approximating arc than MKARC returns the given arc as goo enough;
otherwise MKARC split the arc in two and place a new arc vertex on
the vector vertex tht was furthest away from the original arc.
This manner of smooth collaspes the stair cases of jaggy
quantum edges.
PAGE 33. FIGURES: COMPARING ILLUSTRATED.
1ST Q3
2ND Q4
3RD FUSION Q3 AND Q4
4TH BABY.
PAGE 34. 5. COMPARING.
The compare step of CRE connects the polygons and
arcs of the current image with corresponding polygons and arc
of the previous image. CMPARE solves the problem of correlating
features between two similar images.
CMPARE is composed of four sections:
1. make shape nodes for polygons.
2. compare and connect polygons one to one.
3. compare and connect polygons two to one.
4. compare and connect vertices of two polygons.
First the shape nodes for
all the polygons of the current image are computed; second, the
polygons of each level of the current image are compared with
the corresponding level of the previous image for one to one match;
third, the unmated polygons of the current level aree compared with.
PAGE 35. LAMINA INERTIA TENSOR.
PAGE 36. PERFORMANCE.